The invention relates generally to computer operating systems, and deals more particularly with scheduling of computer program threads for execution in a multitasking operating system.
Single tasking operating systems have been available for many years. In such systems, a computer processor executes computer programs or program subroutines serially, i.e. no computer program or program subroutine can begin to execute until the previous one terminates. This type of operating system does not make optimum use of the computer processor in a case where an executing computer program or subroutine must wait for the occurrence of an external event (such as availability of data or a resource) because processor time is wasted. This problem led to the advent of multitasking or multithreaded operating systems in which each computer program is divided into one or more program threads or streams of execution. Each of the program threads performs a specific task. While a computer processor can execute only one program thread at a time, if the thread being executed must wait for the occurrence of an external event, i.e. the thread becomes "non-dispatchable", execution of the non-dispatchable thread is suspended and the computer processor executes another thread of the same or different computer program to optimize use of itself. Multitasking operating systems have also been extended to multiprocessor environments where threads of the same or different programs can execute in parallel on different computer processors. While such multitasking operating systems optimize the use of the one or more processors, they do not permit the application program developer to adequately influence the scheduling of execution of threads.
U.S. Pat. No. 4,395,757 discloses an information structure called a "semaphore" which is available to an application program developer and serves as a signalling mechanism to coordinate or synchronize a computer process and an event or resource. The semaphore indicates the presence of events or resources waiting for a process to utilize them, or alternately, the presence of a process waiting for events or resources. If more than one event or resource, or process is present at one time, they may be queued awaiting the matching process, or event or resource, respectively.
U.S. Pat. No. 4,658,351 discloses the use of priority levels and semaphores to coordinate tasks in a multitasking operating system. Multiple task queues are established, one for all tasks which are ready to run and have the same priority level. A task control block is generated to represent each task and is stored in the task queue corresponding to the task's priority level. Apparently the sequence of the task control blocks in each task queue is based upon the order in which the corresponding task became ready to run. Tasks are executed in a sequence depending upon the relative priorities of the task queues and upon the locations of the task control blocks in each task queue. Event signalling and message passing are handled by semaphores.
A publication entitled "Scheduling Techniques for Concurrent Systems" by John K. Ousterhout in the Proceedings of the Third International Conference on Distributed Computing Systems, 1982 discloses that program threads are organized into different classes. During a time "slice", all dispatchable program threads from one class or a fragment of the dispatchable threads in one class are executed concurrently on a like number of processors. At the end of a time slice, all executing threads are preempted by other dispatchable threads.
While the foregoing techniques permit an application program developer to influence the order of execution, further improvements are deemed important to permit greater control by the application program developer. Generally, controls placed upon the execution order of the threads, by either the operating system or the application program developer, decrease operating efficiency. Ideally, the operating system should schedule the execution of the threads in as efficient a manner as permitted by the application program.
A general object of the present invention is to provide a multitasking operating system which optimizes the execution of threads, while permitting application programs to substantially influence the execution schedule.
Another object of the present invention is to provide a multitasking operating system of the foregoing types which can operate in either a single processor or multiprocessor computer system.